%%%----------------------------------------------------------
\chapter{Detecting a circle in a noisy binary image}
%%%----------------------------------------------------------
\label{cha:circle}

\section{Problem}
The binary image contains points of a circle and some points which are noise. The points of the circle are not exactly on the circle, they have a deviation (see figure \ref{fig:01_circle-test}). We don't know anything about the circles parameter. The ImageJ filter should find the circle in the picture.

\begin{figure}
	\centering
	\includegraphics[width=.85\textwidth]{01_circle-test}
	\caption{Initial test image}
	\label{fig:01_circle-test}
\end{figure}

\section{Solution}
For this problem there are a lot of more sophisticated circle detection algorithms, for example a Hough transform algorithm. But we will write our own RANSAC based approach. 

At first we collect all Pixels in the picture and store them in an array. Then we choose 3 points randomly, here I tested that these are not the same. With the 3 points $A$, $B$ and $C$ we can calculate the circumscribed circle by using the following equations:
\begin{equation}
D =  2(A_x(B_y-C_y)+B_x(C_y-A_y)+C_x(A_y-B_y))
\end{equation}
\begin{equation}
Ux =  \dfrac{(A^2_x+A^2_y)(B_y-C_y)+(B^2_x+B^2_y)(C_y-A_y)+(C^2_x+C^2_y)(A_y-B_y)}{D}
\end{equation}
\begin{equation}
Uy =  \dfrac{(A^2_x+A^2_y)(C_x-B_x)+(B^2_x+B^2_y)(A_x-C_x)+(C^2_x+C^2_y)(B_x-A_x)}{D}
\end{equation}
Now we count all pixels in the picture that are sufficiently close to the circle.

By repeating this, we will find a circle with the most pixels related to it and the circle gets very likely to be the circle in the image.

\section{Implementation}
The algorithm is implemented as an 8-bit greyscale ImageJ PlugInFilter in the file A01\_Find\_Cirlce.java. When the filter is started an dialog \ref{fig:01_dialog} opens, where the amount of circle calculations and the tolerance can be changed. The points in the image are stored as class of type Point and also the circumscribed circles as class of CircumscribedCircle. For iteration both are stored in ArrayLists. Than the algorithm starts. After the algorithm finished a new image with the found circle will be plotted to a new image \ref{fig:01_outcome} and the parameter of this circle are logged to the ImageJ console.
   
\begin{figure}
	\centering
	\includegraphics[width=.5\textwidth]{01_dialog}
	\caption{Initial dialog to change the parameters}
	\label{fig:01_dialog}
\end{figure} 
\begin{figure}
	\centering
	\includegraphics[width=.5\textwidth]{01_outcome}
	\caption{Circle after 400 search iterations with 0.5 tolerance}
	\label{fig:01_outcome}
\end{figure}

\section{Result}
The present plugin can detect and draw a circle of pixels on a binary image. The reliability of this plugin depends on the parameters. If there are much more pixels off the circle than on the circle (like in picture \ref{fig:01_result_notfound}) than its also hard for the human eye to see the circle.

The amount of calculations and the tolerance are connected to each other. The smaller the tolerance, the more calculation you should make. In figure \ref{fig:01_result_50tries} I simulated how precise the found circle matches to the real one, by increasing the calculations at a fixed tolerance level of 0.05. Every calculation is performed 50 times.

\begin{figure}
	\centering
	\includegraphics[width=.5\textwidth]{01_result_notfound}
	\caption{Circle after 400 search iterations with 0.5 tolerance, 150 pixels on the circle and 4000 of the circle}
	\label{fig:01_result_notfound}
\end{figure}
\begin{figure}
	\centering
	\includegraphics[width=.85\textwidth]{01_result_50tries}
	\caption{Showing the distance in pixel after 50 tries. The x-axis shows the amount of calculations.}
	\label{fig:01_result_50tries}
\end{figure}